#coding = utf-8
dict = {'1':'1','2':'2','3':'3','4':'4','5':'5','6':'6','7':'7','8':'8','9':'9',
      '10':'A','11':'B','12':'C','13':'D','14':'E','15':'F'}
dict_1 =  {'1':'1','2':'2','3':'3','4':'4','5':'5','6':'6','7':'7','8':'8','9':'9',
           'A':'10','B':'11','C':'12','D':'13','E':'14','F':'15'}
def c2i(n,x):   #十进制转换为c进制 返回数组 位次和数组序列成反比
    b = []
    a = []
    while True:
        s = n // x
        y = n % x
        b.append(y)
        if s == 0:
            break
        n = s
    b.reverse()
    for i in range(len(b)):
        a.append(str(b[i]))
    return a

t = int(input('输入测试数据组数'))
while t:
    C = int(input('密码进制'))
    c_n = input('十进制数字')       #第一个测试数字
    M = list(input('数组（空格区分）'))
    while ' ' in M :        #格式化输入
        M.remove(' ')
    for i in range(len(M)):
        M[i] = dict_1[M[i]]
    i = 1
    N = int(c_n)
    while len(str(c_n)) <= 500:
        cv = 1
        c_n = c2i(N*i,C)       #将符合输入十进制数字倍数的数字化为c进制 用于下面进行比较
        for char in c_n:       #比较测试数字化为c进制后是否符合初始数组
            if char not in M :
                cv = 0
        if cv == 1:
            for i in range(len(c_n)):     #格式化输出
                c_n[i] = dict[c_n[i]]
            c_n_end = ''.join(c_n)
            print(c_n_end)
            break
        i += 1
    if len(str(c_n)) > 500:       #在测试数字位数大于500时跳出循环并给出so sorry
        print('so sorry')
    t -= 1